W11. Automata to Grammars

1. Theory

1.1 Non-deterministic Pushdown Automata

1.1.1 Recap: Deterministic PDA

A Deterministic Pushdown Automaton (DPDA) is a 7-tuple where:

• is a finite set of states;
• is a finite input alphabet;
• is a finite stack alphabet;
• is the (partial) transition function — for each state, optional input symbol, and top-of-stack symbol, at most one next configuration is defined;
• is the initial state;
• is the initial stack symbol;
• is the set of accepting states.

The key constraint that makes the automaton deterministic is that the transition function is at most single-valued: for any there is at most one possible move. Additionally, there is a no-conflict rule for -moves: if is defined, then must be undefined for all .

1.1.2 Non-deterministic PDA: Formal Definition

A Non-deterministic Pushdown Automaton (NPDA) is defined with the same 7-tuple structure, but the transition function is allowed to return a set of possible next configurations:

where denotes finite subsets of . The machine may have zero, one, or more possible transitions from any configuration. A string is accepted if at least one possible computation path leads to an accepting state — this is the standard existential acceptance condition.

The crucial difference from DPDA is that the no-conflict constraint for -moves is removed: from state with top-of-stack , both and may simultaneously be non-empty, creating genuine non-determinism.

1.1.3 NPDA versus DPDA: Expressiveness

Non-determinism strictly adds expressive power to PDAs — unlike the situation with finite automata, where NFSA and DFSA recognise exactly the same languages.

The canonical example is . No DPDA can recognise this language, because after reading the s, the automaton would need to simultaneously prepare two different stack configurations (one per , or one per two s). An NPDA handles this by guessing non-deterministically which language the input belongs to: it pushes s (in pairs or singly) and then pops while reading s.

This leads to the fundamental hierarchy:

where CFL (context-free languages) is exactly the class of languages recognisable by NPDAs. DCFLs (deterministic context-free languages) are a proper subset of CFLs.

NPDA for {aⁿbⁿ | n ≥ 1} ∪ {aⁿb²ⁿ | n ≥ 1}: non-deterministic branch on reading the first b

1.2 Closure Properties of NPDA

The class of languages recognised by NPDAs (context-free languages, CFLs) has a fundamentally different closure profile from regular languages and from deterministic CFLs.

1.2.1 Union: NPDA is Closed

Given two NPDAs, NPDA recognising and NPDA recognising , we construct an NPDA for as follows: introduce a new initial state and two -transitions — one into the start state of NPDA and one into the start state of NPDA. On any input, the machine non-deterministically enters one of the two original automata.

CFL is closed under .

1.2.2 Intersection: NPDA is Not Closed

Consider the two languages over :

Their intersection is:

This language is not context-free (it requires a two-counter check that no stack machine can perform). Therefore:

CFL is not closed under .

The underlying reason is that a pushdown stack is a single linear memory. Once it is used to count s against s, it cannot simultaneously count s against s.

1.2.3 Complement: NPDA is Not Closed

This follows immediately from closure under union and non-closure under intersection via De Morgan’s law:

If CFL were closed under complement, then since it is closed under union, it would also be closed under intersection — contradicting the result above. Therefore:

CFL is not closed under complement .

Note: DPDA is closed under complement (swap accepting and non-accepting states after completing the automaton), but NPDA is not, because the existential acceptance condition makes state-swapping unsound. If input is processed non-deterministically along two paths — one accepting, one rejecting — then is accepted. After swapping, path A rejects and path B accepts, so is still accepted, even though it should be rejected in a correct complement.

1.2.4 Difference: NPDA is Not Closed

Since , closure under set difference would imply closure under complement. Because CFL is not closed under complement:

CFL is not closed under .

1.2.5 Closure Table

				complement
Regular (FSA)	yes	yes	yes	yes
DCFL (DPDA)	no	no	no	yes
CFL (NPDA)	yes	no	no	no

1.2.6 Pumping Lemma for Context-Free Languages (Bar-Hillel Lemma)

Just as the pumping lemma for regular languages lets us prove a language is not regular, the Bar-Hillel lemma provides a necessary condition for a language to be context-free. If is recognised by some NPDA, then there exists a constant such that every string with can be decomposed as satisfying:

1. — at least one of is non-empty;
2. — the “pumped” portion is not too long;
3. for every .

Application. is not context-free. Any pumping attempt on a string like would require and to span at most two of the three character types, so pumping changes the counts of at most two letter types, breaking the balance.

1.3 Non-deterministic Turing Machine

1.3.1 Formal Definition

A Non-deterministic Turing Machine (NTM) is obtained from a deterministic TM by modifying only the transition function. The NTM is still the 7-tuple where are defined exactly as in a DTM. The transition function becomes:

Instead of returning a single next configuration, returns a set of possible next configurations (state, tape symbol(s) to write, head direction(s)). For a transducer variant, the output mapping is similarly modified to return a set.

Acceptance condition. A string is accepted by an NTM if and only if at least one of the possible computation paths starting from the initial configuration on input reaches an accepting state. This is again existential nondeterminism: one successful path is sufficient.

1.3.2 Computation Tree

A deterministic TM’s computation on a fixed input traces a single sequence of configurations — a line. An NTM’s computation is a tree: at each step, the machine may fork into multiple branches, one for each element of the set. The tree can expand exponentially with depth.

The acceptance condition says: the input is accepted if any path in the computation tree reaches an accepting (final) state . Paths that halt in a non-accepting state represent rejection on that branch; paths that run forever represent non-terminating branches.

NTM computation tree: a branching structure where any path reaching an accepting configuration (blue square) means the input is accepted

1.3.3 Simulating an NTM with a DTM: Breadth-First Search

Can a deterministic TM simulate a non-deterministic one? The answer is yes, using breadth-first search (BFS) over the computation tree.

Why not depth-first search? A DFS visit follows one branch all the way down. If that branch is infinite (a non-terminating computation), the DFS never backtracks and never explores other branches, potentially missing accepting configurations that exist on other paths. This is analogous to the Halting Problem: you cannot tell in advance whether a branch will be infinite or merely long.

BFS simulation. A DTM simulating the NTM visits all computation tree nodes level by level: first all configurations reachable in 0 steps, then all reachable in 1 step, then 2 steps, and so on. If an accepting configuration exists at any finite depth, BFS will reach it in finite time.

The BFS simulation uses a multi-tape DTM: 1. One tape holds the input string. 2. One tape maintains the queue of configurations to explore (serialised as strings). 3. One tape performs the simulation of each NTM step.

Consequence. Every language recognised by an NTM is also recognised by some DTM. Non-determinism does not add expressive power to Turing Machines, only (potentially exponential) algorithmic speed.

1.3.4 Summary: DTM vs NTM

• DFSA and NFSA: same expressive power (regular languages).
• DPDA and NPDA: different expressive power — NPDA is strictly more powerful.
• DTM and NTM: same expressive power (recursively enumerable languages).

The PDA family is the unique case where determinism and non-determinism produce genuinely different language classes.

1.4 DFSA to Regular Expression: Kleene’s Algorithm

1.4.1 Intuitive Foundation

Every finite automaton can be converted to an equivalent regular expression. The conversion rests on three algebraic observations:

• Union: two parallel edges and can be merged into a single edge .
• Concatenation: a path through an intermediate state can be collapsed into a single edge , eliminating .
• Kleene star: a self-loop means the machine can repeat any number of times, giving the expression .

By systematically eliminating intermediate states using these three rules, the entire automaton is collapsed into a single regular expression labelling a direct edge from the initial state to each accepting state.

1.4.2 Formal Algorithm

Let be a DFSA with .

Base case (). Define as the regular expression for all direct transitions from to :

The on the diagonal () represents the possibility of staying in without reading anything.

Inductive step (). Each iteration “unlocks” paths that may pass through :

Interpretation: captures all paths from to that may visit any of as intermediate states. The first term adds paths that go from to , loop around any number of times, and then proceed to .

Final answer. If is the set of accepting states, the regular expression for is:

Semantic meaning of . The set represents all strings that take from state to state without passing through any state with index greater than (as intermediate states). At there are no restrictions, so represents all strings leading from the start state to .

1.5 -moves and Pushdown Automata

1.5.1 FSA with -Transitions

In this course, PDAs are already defined with -moves (spontaneous transitions that consume no input). For FSAs, -transitions were not considered until now. A Nondeterministic FSA with -moves (NFSA-) allows . However:

All three models recognise exactly the regular languages. -transitions add no power to finite automata.

1.5.2 PDA Sensitivity to Model Variations

Unlike FSAs, PDAs are highly sensitive to seemingly minor variations in the model definition. The following changes all affect the set of recognisable languages:

• Acceptance by final state versus acceptance by empty stack — these are equivalent for NPDAs but not always for DPDAs.
• The number of stacks — a 2-stack PDA already has the power of a TM.
• Deterministic vs non-deterministic — strictly different language classes (DCFL CFL).
• With vs without -moves — removing -moves from DPDAs reduces their power.

This sensitivity makes the PDA family a rich object of study for exploring the boundaries between computational models.

1.5.3 Realtime Deterministic Pushdown Automata

A realtime DPDA is a DPDA without -moves: every transition must consume exactly one input symbol. This strictness means the automaton processes input in real time — no internal work without reading input.

Realtime DPDAs are strictly less powerful than DPDAs with -moves:

Example. The language requires a DPDA but cannot be recognised by any realtime DPDA. In path 2 (the -branch), after reading the machine must pop all -symbols from the stack to retrieve the -count underneath, but it has no input to consume while doing so — -moves are unavoidable.

1.5.4 The Complement of NPDA

For deterministic machines whose computation always terminates, taking the complement is straightforward: complete the automaton (add a dead state) and swap accepting/non-accepting states. This works for DPDA.

For NPDA, this approach fails because of the existential acceptance condition. Consider a non-deterministic computation of along two branches:

• Branch A: accepts.
• Branch B: rejects.

Because of existential nondeterminism, is accepted by the original NPDA. After swapping states, branch A now rejects and branch B accepts — so is still accepted by the swapped automaton, even though it should be rejected for a correct complement. The state-swap approach breaks under non-determinism.

1.5.5 Languages Recognised by NDPDA

Languages recognisable by NDPDAs are exactly the context-free languages (CFLs). CFLs sit strictly between the deterministic CFLs and the recursively enumerable languages.

Language hierarchy: regular ⊊ deterministic CFL ⊊ context-free ⊊ recursively enumerable

1.6 Generative Grammars

1.6.1 Operational vs Generative Models

So far this course has studied operational models (automata): machines that receive input and decide whether to accept it. There is a complementary family of generative models (grammars): sets of rules that produce the strings of a language.

• Automata (operational): answer “Is in the language?”
• Grammars (generative): answer “How can strings of the language be constructed?”

Both views are equally important and, as the Chomsky hierarchy shows, correspond to each other: every automaton class has a corresponding grammar class.

In parsing, grammars define the syntax of programming languages, while automata process source code to check syntactic correctness. Grammars are often nondeterministic, but practical parser generators use carefully designed deterministic grammars with lookahead.

1.6.2 Formal Definition of a Grammar

A formal grammar is a 4-tuple where:

• is the finite nonterminal alphabet (variables; by convention written in upper case);
• is the finite terminal alphabet (the symbols of the generated language; by convention written in lower case);
• is the combined vocabulary;
• is the axiom (initial symbol or start symbol);
• is the finite set of production rules (or rewriting rules), written .

Productions. A production consists of:

• Left-hand side : a string containing at least one nonterminal;
• Right-hand side : any (possibly empty) string of terminals and nonterminals.

The grammar generates strings by repeatedly replacing substrings matching the left-hand side of a production with the corresponding right-hand side.

1.6.3 Immediate Derivation and Language Generated

Immediate derivation. (read “ is obtained by immediate derivation from ”) if and only if:

That is, is rewritten as in the context . The word “context” is intentional: context-sensitive grammars are defined precisely by allowing the left-hand side to carry non-trivial context.

Language generated. Given , the language generated by is:

That is, consists of all strings over the terminal alphabet that can be derived from the axiom in one or more steps, using the productions of in any order.

1.6.4 Chomsky Hierarchy of Grammars

The Chomsky hierarchy classifies grammars by the form of their production rules, creating a nested family of language classes:

Chomsky type	Grammar	Language class	Minimal automaton
Type 0	Unrestricted	Recursively enumerable	Turing Machine
Type 1	Context-sensitive	Context-sensitive	Linear Bounded Automaton
Type 2	Context-free	Context-free	NDPDA
Type 3	Regular	Regular	FSA

Each level is a strict subset of the one above. The class of context-free grammars (Type 2) is particularly important for programming language design: every CFG can be parsed by an NDPDA, and carefully designed deterministic grammars can be parsed efficiently by standard parser generators (LL, LR).

---

2. Definitions

• DPDA (Deterministic Pushdown Automaton): A 7-tuple with transition function ; at most one move from each configuration, with no -conflict.
• NPDA (Non-deterministic Pushdown Automaton): Same structure as DPDA but ; multiple moves allowed from any configuration.
• Context-free language (CFL): A language recognised by some NPDA; equivalently, generated by a context-free grammar (Type 2 Chomsky).
• Deterministic context-free language (DCFL): A language recognised by some DPDA; a proper subset of the CFLs.
• Bar-Hillel (pumping) lemma: If is a CFL, there exists such that any with can be split with , , and for all .
• NTM (Non-deterministic Turing Machine): A TM with returning a set of configurations; accepts if any computation path reaches .
• Computation tree: The branching tree of all possible NTM configurations reachable from the initial configuration; accepted if any node in the tree is an accepting configuration.
• Existential nondeterminism: Acceptance criterion requiring that at least one computation path accepts (standard for NFSA, NPDA, NTM).
• BFS simulation: A DTM technique for simulating an NTM by exploring the computation tree level by level, guaranteeing discovery of any accepting configuration at finite depth.
• Kleene’s Algorithm: A procedure that converts a DFSA with states into an equivalent regular expression by computing for , where denotes all strings taking from to via intermediate states with index at most .
• : Base-case expressions in Kleene’s algorithm; captures only direct (single-step) transitions between and (plus on the diagonal).
• Realtime DPDA: A DPDA without -moves; every transition consumes exactly one input symbol; strictly less powerful than DPDA with -moves.
• Formal grammar: A 4-tuple with nonterminals, terminals, productions, and start symbol; generates a language by rewriting.
• Production: A rewriting rule where contains at least one nonterminal and is any string of terminals and nonterminals.
• Axiom (start symbol): The nonterminal from which all derivations begin.
• Immediate derivation (): if is obtained from by applying a single production in some context.
• Language generated by : — all terminal strings derivable from in one or more steps.
• Chomsky hierarchy: Four-level classification of grammars (Type 0–3) corresponding to TM, LBA, NPDA, and FSA respectively.

---

3. Formulas

• NPDA transition function:
• NTM transition function ( tapes):
• NTM acceptance: accepted computation path in the tree of on reaching a state in
• Kleene base case:
• Kleene inductive step:
• Kleene final answer: where
• Language of grammar:
• Productions domain:
• Immediate derivation:

---

4. Practice

4.1. Build NPDAs for Three Languages (Lab 10, Task 1)

Build NPDAs that recognise the following languages:

1. , where is the reverse of .

2. .

3. .

Click to see the solution

(a) — even-length palindromes.

The key idea: the NPDA non-deterministically guesses the midpoint of the string. In the first half it pushes every symbol onto the stack; in the second half it pops and matches. Since , both halves are non-empty.

• States: (push phase), (pop phase), (accepting).
• Push phase ():
  • and and — push for each .
  • and and — push for each .
  • Non-deterministic -transitions to : , , — guess the midpoint (spontaneous move).
• Pop phase ():
  • — match against on stack.
  • — match against on stack.
• Acceptance (): — accept when stack is back to (all symbols matched).

The NPDA is correct because the -transitions allow it to guess the midpoint at any position; along the correct branch the stack will empty exactly when is consumed.

(b) .

Use the union construction: non-deterministically choose one of two branches at the start.

• Common start : pushes two s per read (self-loops: ; ).
• Branch for (transition ): pop one per ; accept when is exposed.
  • : self-loop ; transition .
• Branch for (transition , then ): pop one per two s; accept when is exposed.
  • .

Since the initial push phase doubles the count ( per ), popping one per in the first branch gives s, and the alternating two--per- pattern in the second branch gives s.

(c) .

Use the union where (count against ) and (count against ). Non-deterministically choose:

• Branch A (): push for each ; read s without touching stack; pop for each ; read s freely; accept when stack empties.
• Branch B (): read s freely; push for each ; read s freely; pop for each ; accept when stack empties.

Each branch is a standard DPDA; the NPDA is their union via a shared initial state with two -outgoing transitions.

4.2. Build NTMs for Two Languages (Lab 10, Task 2)

Build NTMs that recognise the following languages:

1. — strings that are the concatenation of a non-empty word with itself.

2. — even-length palindromes.

Click to see the solution

(a) .

The string must have even length and the first and second halves must be identical. A standard DTM approach uses multiple passes, but an NTM can guess the midpoint.

Two-tape NTM construction:

1. Non-deterministically guess the midpoint: the NTM writes a marker at some position in the input (guessing where the first half ends and the second half begins).
2. Copy the first half onto tape 2.
3. Compare tape 2 with the second half symbol by symbol.
4. Accept if and only if the comparison succeeds and both halves have the same length.

Along the correctly-guessing branch, the NTM accepts; along all other branches, it rejects. By existential acceptance, the NTM accepts if any branch succeeds.

(b) .

Similar to (a), but the second half must be the reverse of the first.

Two-tape NTM construction:

1. Non-deterministically guess the midpoint.
2. Copy the first half onto tape 2 in reversed order (write symbols right-to-left on tape 2).
3. Compare tape 2 with the second half symbol by symbol (left to right).
4. Accept if the comparison succeeds.

Alternatively, a single-tape NTM can: 1. Non-deterministically guess the midpoint and mark it. 2. Check the first symbol against the last, the second against the second-to-last, etc. by traversing back and forth and marking matched pairs.

4.3. Build NPDA for a Union Language (Lab 10, Homework 1)

Build an NPDA that recognises the language:

Click to see the solution

The language is a union of two simpler languages:

• : the empty string plus for .
• : strings of even-length blocks of s (including ).

NPDA construction via union:

Introduce a new start state with -transitions into the start states of two sub-automata.

Sub-automaton for (standard DPDA for ):

• : push per . Transition to on first .
• : pop per . Transition to accepting state when stack is .
• (accepting): also accept from via transition.

Sub-automaton for (even number of s):

• (accepting): read , go to .
• : read , return to (accepting).
• Stack operations: push/pop a marker each two s, or simply use the state to count parity (no stack needed beyond ).

Accepting states of sub-automaton: (after even number of s, including zero).

The full NPDA:

• and .
• Internally each sub-automaton works as described.

Both and the empty string are accepted (both with empty stack and are accepting states reachable from on ).

4.4. Build NTM for a Union of Counting Languages (Lab 10, Homework 2)

Build an NTM that recognises the language:

Click to see the solution

The language requires the NTM to non-deterministically choose which sub-language the input belongs to, then verify deterministically.

Non-deterministic choice. At the outset, the NTM non-deterministically branches into two computation paths:

• Path A: verify .
• Path B: verify .

Verification of (Path A) on a 2-tape TM:

1. Scan tape 1 to find the number of s: mark each on tape 1 and write a tally mark on tape 2.
2. For each , erase one tally on tape 2.
3. Accept if tape 2 is empty exactly when all s are consumed.

Verification of (Path B) on a 2-tape TM:

1. Scan s and write two tally marks on tape 2 per .
2. For each , erase one tally on tape 2.
3. Accept if tape 2 is empty exactly when all s are consumed.

Both sub-computations can be implemented as standard deterministic TM procedures. The NTM wraps them with a non-deterministic initial branch. Since the language is a union, if either path accepts, the input is accepted.

4.5. DPDA for (Tutorial 10, Example 1)

Construct a DPDA for and trace its behaviour on the string .

Click to see the solution

States: (push phase), (pop phase), (accepting).

Transition function:

• — push first onto .
• — push additional .
• — switch to pop phase on first ; pop .
• — continue popping for each .
• — stack returned to initial symbol; accept.

Trace on :

Step	Input	State	Stack (top first)
0
1
2
3
4
5

The DPDA reaches (accepting) with an empty remaining input. ✓

4.6. NPDA for (Tutorial 10, Example 2)

Construct an NPDA for using a non-deterministic -transition to switch phases, and explain how this differs from the DPDA version.

Click to see the solution

States: (push phase), (pop phase), (accepting).

Transition function:

• and — push for each .
• Non-deterministic spontaneous move: — non-deterministically guess that all s have been read and switch to the pop phase (without consuming input).
• — pop for each .
• — accept when stack is .

Difference from DPDA. In the DPDA, the switch from push to pop is triggered by actually reading the first . In this NPDA, the switch happens via an -transition at any point during the -reading phase. Along most branches the guess will be wrong and those paths reject; only the branch where the -transition fires after exactly s will correctly enter the pop phase and accept .

This is the canonical illustration of how non-determinism can “guess” structural boundaries that a deterministic machine would determine by reading input.

4.7. NPDA for Even-Length Palindromes (Tutorial 10, Example 3)

Construct an NPDA for and explain why no DPDA can recognise this language.

Click to see the solution

States: (push phase), (pop / match phase), (accepting).

Push phase transitions (, push symbol onto stack for each input symbol):

Input	Top of stack	New stack top	Meaning
			push
			push
			push
			push
			push
			push

Non-deterministic midpoint transitions (from to , -moves):

• , , — guess the midpoint at any time.

Pop / match phase ():

• — input matches on stack; pop.
• — input matches on stack; pop.

Acceptance: — accept when stack is (all symbols matched).

Why no DPDA can recognise this. A DPDA would need to know exactly when the middle of the string occurs. For the string , the midpoint is between the two s. But for and , the midpoint positions are different, and without a separator (like ), a deterministic machine cannot tell when to stop pushing and start popping. The non-deterministic -transitions allow the NPDA to “guess” the midpoint on every possible branch; exactly one correct branch accepts.

4.8. Kleene’s Algorithm on a 2-State Automaton (Tutorial 10, Example 4)

Apply Kleene’s Algorithm to the DFSA with defined by: is the start and accepting state; has a self-loop on ; there is a transition ; there is a transition .

Compute for all at steps , , and , and state the final regular expression.

Click to see the solution

Step (direct transitions only).

• — self-loop on , plus (stay in by reading nothing).
• — direct edge on .
• — direct edge on .
• — no self-loop, only (stay in ).

Step (paths may now pass through ).

Apply :

Step (paths may now pass through and ).

Apply :

Final answer. The accepting state set is , so the answer is .

This is the language of all strings over where every is followed by at least one — equivalently, no string ends in (every appears within a block ).

4.9. Kleene’s Algorithm on a 3-State Automaton (Tutorial 10, Example 5)

Apply Kleene’s Algorithm to the DFSA with , accepting states , and transitions:

• (self-loop),
• (self-loop),
• ,

Compute all values through and give the final regular expression.

Click to see the solution

Step .

• , ,
• , ,
• , ,

Step (unlocking paths through ).

Using :

• , ,

Step (unlocking paths through and ).

Using :

• ,

Step (unlocking all paths through , , ).

Key computation for the final answer (accepting states are and ):

Final answer. Since :

This is the language of strings that start with any number of s, then have at least one , and continue with blocks of the form , optionally ending with one more .